//Evaluate the value of an arithmetic expression in Reverse Polish Notation. 
//
// Valid operators are +, -, *, and /. Each operand may be an integer or another
// expression. 
//
// Note that division between two integers should truncate toward zero. 
//
// It is guaranteed that the given RPN expression is always valid. That means th
//e expression would always evaluate to a result, and there will not be any divisi
//on by zero operation. 
//
// 
// Example 1: 
//
// 
//Input: tokens = ["2","1","+","3","*"]
//Output: 9
//Explanation: ((2 + 1) * 3) = 9
// 
//
// Example 2: 
//
// 
//Input: tokens = ["4","13","5","/","+"]
//Output: 6
//Explanation: (4 + (13 / 5)) = 6
// 
//
// Example 3: 
//
// 
//Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
//Output: 22
//Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
//= ((10 * (6 / (12 * -11))) + 17) + 5
//= ((10 * (6 / -132)) + 17) + 5
//= ((10 * 0) + 17) + 5
//= (0 + 17) + 5
//= 17 + 5
//= 22
// 
//
// 
// Constraints: 
//
// 
// 1 <= tokens.length <= 104 
// tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the 
//range [-200, 200]. 
// 
// Related Topics 栈 
// 👍 342 👎 0


package leetcode.editor.cn;

import java.util.Stack;

//Java：Evaluate Reverse Polish Notation
class P150EvaluateReversePolishNotation {
    public static void main(String[] args) {
        Solution solution = new P150EvaluateReversePolishNotation().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int evalRPN(String[] tokens) {
            Stack<String> stack = new Stack<>();
            if (tokens == null || tokens.length == 0) {
                return 0;
            }
            for (String token : tokens) {
                if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
                    int back = Integer.parseInt(stack.pop());
                    int front = Integer.parseInt(stack.pop());
                    int val = 0;
                    switch (token) {
                        case "+":
                            val = front + back;
                            break;
                        case "-":
                            val = front - back;
                            break;
                        case "*":
                            val = front * back;
                            break;
                        case "/":
                            val = front / back;
                            break;
                    }
                    stack.push(String.valueOf(val));
                }
                else{
                    stack.push(token);
                }
            }
            return Integer.parseInt(stack.pop());
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}